package String;

public class p459重复的子字符串 {
    // 方法1：移动匹配
    // 如果一个字符串中的重复子串能够组成整个字符串，那么两个相同的字符串连接在一起，中间组合部分一定可以再次组合成一个完整的字符串
    // 但是需要将组合之后的首位字符去掉，这样就不会被原来的两个字符串所干扰
    class Solution1 {
        public boolean repeatedSubstringPattern(String s) {
            return (s + s).substring(1, 2 * s.length() - 1).contains(s);
        }
    }

    // 方法2：KMP
    class Solution2 {
        public boolean repeatedSubstringPattern(String s) {
            if("".equals(s)) return false;
            int len = s.length();
            int[] next = new int[len];
            getNext(next, s);
            // 注意判断next[len - 1] > 0或者说是 ！= 0【排除整个字符串没有重复的子串的情况】
            // 后面的len % (len - next[len - 1])无法排除自身除自身的情况
            return next[len - 1] > 0 && len % (len - next[len - 1]) == 0;
        }

        public void getNext(int[] next, String s){
            // 初始化前缀下标和next数组的第一个元素
            int j = 0;
            next[0] = 0;
            // 最长前缀不相等的情况【一直回退，直到回退到第一个元素或者上一次相等情况的位置】
            for(int i = 1; i < s.length(); i++){
                while(j > 0 && s.charAt(j) != s.charAt(i)){
                    j = next[j - 1];
                }
                // 最长前缀相等的情况【代表前缀的下标j = j + 1】
                if(s.charAt(j) == s.charAt(i)){
                    j++;
                }
                // 填充next数组
                next[i] = j;
            }
        }
    }
}
